As the amount of data in computing systems continues to increase, there is a strong desire for improvements that allow datasets to be efficiently processed. DRAM (Dynamic Random Access Memory) and the like are often too small to efficiently process large data sets. Algorithms that process data out-of-core (e.g., using Hard Disk Drives (HDDs)) tend to be slow.
One potential solution is to introduce flash memory into the computing systems. Flash memory is faster than HDDs and has the capacity to accelerate dataset analysis. Even though flash memory can improve the processing capability of the computing systems, flash memory has several problems that impact performance.
Conventional data structures are designed assuming that random changes or random edits can be performed quickly and without penalty. In contrast, there is a penalty associated with small edits or changes in a flash memory. Small edits in a flash memory require the entire edited page to be copied forward to a new page. The previous page must be eventually erased before it can be reused. More specifically, data in a used area or page of a conventional flash memory cannot be simply changed to a new value. Rather, it is necessary to erase the entire page before writing the data to the page. This is the reason that small edits to a page in the flash memory are performed by writing the data to a new page. It then becomes necessary to erase the old page.
This process causes both a performance penalty and a lifespan penalty. This process results in multiple reads and writes (thus the performance penalty). The lifespan penalty occurs because flash memory can only be written or erased a limited number of times before wearing out. Further, flash memory is typically erased in large units.
This creates additional problems when implementing data structures in the flash memory. Every time a change is made to data that is stored in the data structure, there is a potential for multiple writes and erasures.
In addition, many computing systems and applications support concurrently executing applications or threads. To prevent two applications or threads from accessing the same data structure at the same time, it is necessary to ensure that only one application or thread has access to the data structure at a time. This is achieved using a lock in some systems. Unfortunately, a conventional lock in flash memory is subject to the same performance and lifespan penalties as other data structures. Each change to the lock would effectively require the entire lock to be recreated at another location in the flash memory. Systems and methods are needed to improve the performance of flash memory and to improve the lifespan of the flash memory and to effectively implement data structures in a flash memory.